package com.cat.dataStructure02;

import java.util.Arrays;

/**
 *   @description https://leetcode.cn/problems/count-primes/
 *   @author 曲大人的喵
 *   @create 2025/10/10 10:42
 *   @since JDK17
 */

public class Solution08 {
    static int N = ((int) (5e6 + 10));
    static boolean[] vis = new boolean[N];
    public int countPrimes(int n) {
        int ans = 0;
        Arrays.fill(vis, 0, n + 1, false);
        for (int i = 2; i * i <= n; i++) {
            if (!vis[i]) {
                for (int j = i * i; j <= n; j += i) {
                    vis[j] = true;
                }
            }
        }
        for (int i = 2; i < n; i++) {
            ans += vis[i] ? 0 : 1;
        }
        return ans;
    }
}
